package solution.s_144;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树的前序遍历 - 非递归实现
 * 解题思路：
 *      设置一个当前元素的指针，首先指向根节点。
 *      只要当前节点不为空，就讲当前节点添加到结果中。
 *      然后判断当前节点的左子树，假如左子树不为空，那么将当前节点入栈，然后将当前节点指针指向左子树，再次循环，遍历左子树。
 *      直到左子树遍历完成，然后就判断当前的右子树，假如右子树不为空，九江当前节点的指针指向右子树，循环遍历右子树。
 *      直到左子树和右子树遍历完成，那么也表示以当前这棵树为左子树的树的根节点和左子树都已经遍历完成。
 *      而以当前这棵树为左子树的树便是栈顶的元素。
 *      假如此时栈中已经没有元素，那表示整棵树已经遍历完成。
 *      假如栈中还有元素，将栈顶元素出栈，假如出栈的元素的右子树为空，就再次出栈元素，直到找到需要的元素或者栈为空。
 *      这时假如元素的右子树还是为空，表示整棵树遍历完成。
 *      假如出栈元素的右子树不为空，将当前元素指向栈顶元素的右子树，再次循环遍历
 */
public class Solution20201027 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) { return result; }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;
        while (curNode != null) {
            // 添加当前节点的 val 值
            result.add(curNode.val);

            // 假如左子树不为空，将当前节点指向左子树，进行下一次循环
            if (curNode.left != null) {
                stack.push(curNode);
                curNode = curNode.left;
                continue;
            }

            // 左子树遍历完，遍历右子树
            if (curNode.right != null) {
                curNode = curNode.right;
                continue;
            }

            // 左右子树都遍历完的时候，假如此时栈为空，那表示整棵树遍历完成
            if (stack.isEmpty()) {
                break;
            }

            // 出栈当前元素的根元素
            TreeNode treeNode = stack.pop();

            // 假如右子树为空，并且栈不为空的时候，一直寻找，找到需要的那个元素或者栈为空。
            while (treeNode.right == null && ! stack.isEmpty()) {
                treeNode = stack.pop();
            }

            // 假如遍历完，右子树还是为空，表示整棵树遍历完成。
            if (treeNode.right == null) {
                break;
            }

            // 假如右子树不为空，将当前节点指向根元素的右子树，遍历根元素的右子树
            curNode = treeNode.right;
        }

        return result;
    }
}
